extends templates/main.jade

block head
  include templates/katex.jade

block title
  | Quantum Games | xigoi

block content
  h1 Quantum Games
  h2 Quantum tic-tac-toe
  p Some time ago, I discovered the game of 
    a(href="https://en.wikipedia.org/wiki/Quantum_tic-tac-toe") quantum tic-tac-toe
    |  on Quora. It's played like regular tic-tac-toe, but instead of writing one mark, each player writes two small marks labeled with a unique number, which represent a mark in superposition. There may be multiple small marks in one space and whenever they create a cycle, the player who did not create the cycle can choose the way they will be collapsed — that is, write one regular mark for each pair of small marks in the cycle. If this destroys any other small marks, their counterpart will also turn into a regular mark, and this can chain. The rulas for winning are as usual — three regular marks in a row. It may even happen that both players win at once.
  h2 Quantum chess
  p When I played quantum tic-tac-toe with my friend, the idea really intrigued us and we wondered how the same concept could apply to a more complex game. And what better game to use for this purpose than chess? So we quickly decided on the rules, took out a chessboard and started playing. Unfortunately, we didn't finish the game, but here is a rough idea of the rules:
  ul
    li In their turn, a player can choose between doing a quantum move and a collapse.
    li A <dfn>quantum move</dfn> consists of choosing two moves that could be played in regular chess and writing them down. This will create two possible positions. When there are already multiple positions, the player can make any two moves that are valid in <em>some</em> positions and they will be applied to all positions where they're legal.
    li With a <dfn>quantum collapse</dfn>, the player can choose a quantum move and discard one of the possible moves, which will also remove all possible positions resulting from this move and makes the other move the reality. If it turns out that some other move is now impossible, it will also be discarded, and this can chain.
    li A player wins when the opponent's king is captured in <em>all</em> possible positions. Note that the usual rules of check and checkmate would not get on well with quantum chess where a piece may or may not be somewhere, so all rules associated with check and checkmate (such and the king being unable to move through an endangered position when castling) are done away with.
  h2 Generalized quantum games
  p We soon realized that these rules are not very precise and result in a lot of ambiguity. Therefore, we decided to formalize them. However, since the quantum part is pretty much separate from the rules of normal chess, why not define it in a way that can be used for all games? (Or at least for all deterministic turn-based games.) Therefore, we came up with the concept of game quantumification.
  p First, we need a formal idea of a game. I haven't really studied much game theory, so excuse me for using non-standard definitions and symbols.
  ul
    li A <dfn>game</dfn> consists of a set of states \(S\) and moves \(M\) and is played by a sequence of players \(P\).
    li There is always a current state \(s_c \in S\) and a current player \(p_c \in P\).
    li A <dfn>move</dfn> \(m \in M\) is a partial function \(S \to S\).
    li There is a set of <dfn>available moves</dfn> \(M_a(s_c,p_c) \subseteq M\) that depends on the current state and player. The set may be empty.
    li The current player is allowed to choose one move \(m \in M_a\). The current state is then changed to \(m(s_c)\) and the current played is changed based on rules that depend on the game — usually to the cyclically next player in the sequence \(P\).
    li Some states are <dfn>final</dfn>. When the game reaches a final state, certain players win and certain players lose, depending on the game.
